#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <assert.h>

#include "model.h"
#include "mylog.h"

#define FREQ_MAX	(2079997)
#define SMOOTH		(0.1)
#define TEMP		((double)1/FREQ_MAX)
#define _I_			(0xFFFFFFFF)

#define WEIGHTING(cur, gram)										\
				( -log(SMOOTH*(1+cur)/(FREQ_MAX+80000)+(1-SMOOTH)*	\
				((1-TEMP)*(gram)/(1+cur)+TEMP))*1000 )

mod * mod_new(slab * slabp, dat * datp, result * resp, ctx * ctxp, 
					ctx * nrp, ctx * nsp, ctx * trp)
{
	assert(slabp != NULL && datp != NULL && resp != NULL && ctxp != NULL);

	mod * p = (mod *)malloc(sizeof(struct mod));
	if(p == NULL){
		return NULL;
	}
	memset(p, 0, sizeof(struct mod));
	INIT_LIST_HEAD(&p->top);
	p->slabp = slabp;
	p->datp = datp;
	p->resp = resp;
	p->ctxp = ctxp;
	p->nrp = nrp;
	p->nsp = nsp;
	p->trp = trp;
	p->vnum = VIDX_END + 1;
	p->cnum = 0;
	return p;
}

int mod_free(mod * p)
{
	if(p == NULL){
		return -1;
	}
	memset(p, 0, sizeof(struct mod));
	free(p);
	return 0;
}

static edge * edge_new(slab *p, unsigned short vidx_next, int freq)
{
	assert(p != NULL && vidx_next > VIDX_BEG);
	
	edge * e = slab_alloc(p, sizeof(struct edge), SLAB_EDGE);
	if(e == NULL){
		return NULL;
	}
	e->vidx_next = vidx_next;
	e->freq = freq;
	return e;
}

static int edge_push(vertex * v, unsigned short vidx_next, int freq, slab * p)
{
	assert(v != NULL && p != NULL && vidx_next > VIDX_END);
	edge * e = edge_new(p, vidx_next, freq);
	if(e == NULL){
		return -1;
	}
	list_add_tail(&e->list, &v->edge_list);
	return 0;
}

static edge * edge_get(vertex * v, unsigned short vidx_next)
{
	assert(v != NULL && vidx_next > VIDX_END);

	if(list_empty(&v->edge_list)){
		return NULL;
	}
	struct list_head * l = v->edge_list.next;
	edge * e = NULL;
	while(l != &v->edge_list){
		e = list_entry(l, edge, list);
		if(e->vidx_next == vidx_next){
			return e;
		}
		l = e->list.next;
	}
	return NULL;
}

//return vidx
static unsigned short vmap_set(mod * p, vertex * v)
{
	assert(p != NULL && v != NULL);
	
	if(v->len == 0 && v->off == p->cnum){
		v->vidx = VIDX_END;
		p->vmap[VIDX_END] = v;
		return VIDX_END;
	}
	v->vidx = p->vnum ++;
	p->vmap[v->vidx] = v;
	return v->vidx;
}

static vertex * vmap_get(mod * p, unsigned short vidx)
{
	assert(p != NULL);

	return p->vmap[vidx];
}

static vertex * vertex_new(slab *p, unsigned short off, unsigned short len, 
							int freq, unsigned char untype)
{
	assert(p != NULL && (len != 0 || untype == UN_NONE));
	vertex * v = slab_alloc(p, sizeof(struct vertex), SLAB_VERTEX);
	if(v == NULL){
		return NULL;
	}
	INIT_LIST_HEAD(&v->nr_list);
	INIT_LIST_HEAD(&v->ns_list);
	INIT_LIST_HEAD(&v->tr_list);
	INIT_LIST_HEAD(&v->edge_list);
	v->off = off;
	v->len = len;
	v->vidx = 0;
	v->untype = untype;
	v->color = COLOR_WHITE;
	v->freq = freq;
	v->rolei = 0;
	v->ungrami = 0;
	return v;
}

static role * role_new(slab *p, unsigned int id, int freq)
{
	assert(p != NULL);

	role * r = slab_alloc(p, sizeof(struct role), SLAB_ROLE);
	if(r == NULL){
		return NULL;
	}
	r->id = id;
	r->freq = freq;
	return r;
}
#define ROLE_UNI(freq, id, ctxp)	\
	((-log((double)freq+1) + log((double)ctx_get_uni(ctxp,id)+1)) * 1000)

#define ROLE_BI(id0, id1, ctxp)		\
	ctx_get_bi(ctxp, id0, id1)
//	((-log((double)ctx_get_bi(ctxp, id0, id1)+1) + log((double)ctx_get_uni(ctxp,id0)+1)) * 1000)


/*
int ROLE_UNI(int freq, unsigned id, const ctx * ctxp){	
	assert(freq <= ctx_get_uni(ctxp,id));
	return ((-log((double)freq+1) + log((double)ctx_get_uni(ctxp,id)+1)) * 1000);
}

int ROLE_BI(unsigned int id0, unsigned int id1, const ctx * ctxp){
	assert(ctx_get_bi(ctxp, id0, id1) <= ctx_get_uni(ctxp,id0));
	return ((-log((double)ctx_get_bi(ctxp, id0, id1)+1) + log((double)ctx_get_uni(ctxp,id0)+1)) * 1000);
}
*/

static int role_push(vertex * v, enum TAG_STATE st,
						unsigned int id, int freq, mod * p)
{
	assert(v != NULL && p != NULL);
	struct list_head * list = NULL;
	const ctx * ctxp = NULL;
	switch(st){
	case TAG_NR: list = &v->nr_list; ctxp = p->nrp; break;
	case TAG_NS: list = &v->ns_list; ctxp = p->nsp; break;
	case TAG_TR: list = &v->tr_list; ctxp = p->trp; break;
	default: return -1;
	}
	freq = ROLE_UNI(freq, id, ctxp);
	role * r = role_new(p->slabp, v->len==0?ctxp->num-1:id, freq);
	if(r == NULL){
		return -2;
	}
	list_add_tail(&r->list, list);
	return 0;
}

static vertex * graph_get(mod * p, unsigned short off, 
							unsigned short len)
{
	assert(p != NULL);
	if(len == 0){
		return NULL;
	}

	struct list_head * list = p->graph + off;
	if(list_empty(list) || list->next == NULL || ((len < sizeof(unsigned int)) && !(p->bitmap[off] & (1<<len))) ){
		return NULL;
	}
	struct list_head * l = list->next;
	vertex * v = NULL;
	while(l != list){
		v = list_entry(l, vertex, list);
		if(v->len == len){
			return v;
		}
		l = v->list.next;
	}
	return NULL;
}

static vertex * graph_push(mod * p, unsigned short off, 
						unsigned short len, int freq, unsigned char untype)
{
	assert(p != NULL && (len != 0 || (off == p->cnum && untype == UN_NONE)));
	struct list_head * list = p->graph + off;
	vertex * v = graph_get(p, off, len);
	if(v != NULL){
		if(freq > v->freq){
			v->freq = freq;
		}
		v->untype = untype;
		return v;
	}
	v = vertex_new(p->slabp, off, len, freq, untype);
	if(v == NULL){
		return NULL;
	}
	if(list->next == NULL){
		INIT_LIST_HEAD(list);
		p->bitmap[off] = (1<<len);
	}else{
		p->bitmap[off] |= (1<<len);//|=FIXME
	}
	list_add_tail(&v->list, list);
	vmap_set(p, v);
	return v;
}

int mod_push(mod * p, unsigned int off, unsigned short len, 
				int var, enum PUSH_TYPE type)
{
	assert(p != NULL && (len != 0 || (off == p->cnum 
							&& var == UN_NONE && type == PUSH_UNKNOWN)));
	if(off + len > MODEL_SIZE_MAX){
		return -1;
	}

	vertex * v = NULL;
	unsigned int step = 0;
	//for gram
	vertex * v0 = NULL;
	vertex * v1 = NULL;
	unsigned char	untype = UN_NONE;	//-- for untype & char
	int				freq = 0;			//-- for untype & char
	const tag_head * headp = NULL;		//-- for tag
	int				grami = 0;			//-- for tag
	switch(type){
	case PUSH_TAG:		goto TAG;
	case PUSH_UNKNOWN:	goto UNKNOWN;
	case PUSH_CHAR:		goto CHAR;
	}
UNKNOWN:
	untype = (unsigned char)var;
	freq = ctx_get_uni(p->ctxp, untype);
CHAR:
	v = graph_push(p, off, len, freq, untype);
	if(v == NULL){
		return -2;
	}
	return 0;
TAG:
	headp = HEADAT(p->datp, var);
	assert(headp != NULL);
	grami = headp->grami;
	while(grami > 0){
		const tag_node * tagp = TAGAT(p->datp, grami);
		unsigned int tagk = TAGK(tagp->id);
		unsigned int tagv = TAGV(tagp->id);
		//make sure the order: 1.pos 2.gram 3.role 4.untype
		if(step < tagk){
			step = tagk;
		}else if(step > tagk){
			//LOGIT();
			continue;	//wrong order!!!
		}
		switch(step){
		case TAG_POS:
			//add or update graph
			v = graph_push(p, off, len, tagp->freq, UN_NONE);
			if(v == NULL){
				return -3;
			}
			step ++;	//make sure pos once
			break;
		case TAG_GRAM:
			v0 = graph_get(p, off, tagv);
			if(v0 == NULL){
				//return -4;
				break;//some words appear in bi but not uni
			}
			//get or add
			v1 = graph_push(p, off + tagv, len - tagv, 0, UN_NONE);
			if(v1 == NULL){
				return -5;
			}

			if(edge_push(v0, v1->vidx, tagp->freq, p->slabp) < 0){
				return -6;
			}
			break;
				default:
			break;
		}//switch
		grami = tagp->tagi;
	}//while
	if(headp->rolei != 0 || headp->ungrami != 0){
	//word only in role.dct but not in uni.dct
		if(v == NULL){
			v = graph_push(p, off, len, 0, UN_NONE);
			if(v == NULL){
				return -7;
			}
		}
		assert(v != NULL);
		v->rolei = headp->rolei;
		v->ungrami = headp->ungrami;
	}
	return 0;
}

int kbest_path(mod * p)
{
	assert(p != NULL);
	memset(p->graph, 0, sizeof(struct list_head) * (p->cnum));

	unsigned short vidx = VIDX_END;
	vertex * v = NULL;
	struct list_head * list = NULL;
	int i;
	for(i = 0; i < p->vnum + 1; i ++){
		vidx = p->prev[vidx];
		if(vidx == VIDX_BEG){
			break;
		}
		v = vmap_get(p, vidx);
		if(v == NULL){
			return -1;
		}
		v->color = COLOR_WHITE;
		
		list = p->graph + v->off;
		if(list->next == NULL){
			INIT_LIST_HEAD(list);
			p->bitmap[v->off] = (1<<v->len);
		}else{
			p->bitmap[v->off] += (1<<v->len);//|=
		}
		list_add_tail(&v->list, list);
	}
	if(vidx != VIDX_BEG){
		return -2;
	}
	return 0;
}

//return ungram freq
int mod_get_ungram(mod * p, vertex * v, enum UNKNOWN_TYPE st, enum UNKNOWN_DIRECT direct)
{
	int tagi =  v->ungrami;
	int	unarr = UNST2ARR(st, direct);
	while(tagi > 0){
		const tag_node * tagp = TAGAT(p->datp, tagi);
		if(TAGK(tagp->id) != TAG_UNGRAM){
			break;
		}
		if(TAGV(tagp->id) == unarr){
			return tagp->freq;
		}else if(TAGV(tagp->id) > unarr){
			break;
		}
		tagi = tagp->tagi;
	}
	return 0;
}

int mod_get_weight(mod * p, vertex * v0, vertex * v1)
{
	assert(v1 != NULL);
	int uni = 0;
	int bi = 0;
	if(v0 == NULL){			//begin 
		uni = ctx_get_uni(p->ctxp, UN_NONE);
		if(v1->untype || v1->vidx == VIDX_END){
			bi = ctx_get_bi(p->ctxp, UN_NONE, v1->untype);
		}else{
			bi = mod_get_ungram(p, v1, UN_NONE, UN_HEAD);
		}
		return WEIGHTING(uni, bi);
	}
	//v0 != NULL
	uni = v0->freq;

	//!!!As limited corpus, no 'word@end##end' is better
	if(v1->vidx == VIDX_END){
		bi = 0;
	}else if(v0->untype && v1->untype){
		bi = ctx_get_bi(p->ctxp, v0->untype, v1->untype);
	}else if(v0->untype){
		bi = mod_get_ungram(p, v1, v0->untype, UN_HEAD);
	}else if(v1->untype){
		bi = mod_get_ungram(p, v0, v1->untype, UN_TAIL);
	}else{//bigram here
		edge * e = edge_get(v0, v1->vidx);
		if(e == NULL){
			bi = 0;
		}else{
			bi = e->freq;
		}
	}
	return WEIGHTING(uni, bi);
}

int mod_set_cnum(mod * p, unsigned int off)
{
	assert(p != NULL);
	p->cnum = off;
	if(off > MODEL_SIZE_MAX){
		return -1;
	}
	//avoid punctures
	INIT_LIST_HEAD(p->graph + p->cnum);
	if(mod_push(p, off, 0, UN_NONE, PUSH_UNKNOWN) < 0){
		return -2;
	}
	return 0;
}

int mod_clear(mod * p)
{
	memset(p->graph, 0, sizeof(struct list_head) * (p->cnum + 1));
//	memset(p->graph, 0, sizeof(p->graph));
	slab_clear(p->slabp, sizeof(struct vertex), SLAB_VERTEX);
	slab_clear(p->slabp, sizeof(struct edge), SLAB_EDGE);
	slab_clear(p->slabp, sizeof(struct role), SLAB_ROLE);
	p->vnum = VIDX_END + 1;
	p->cnum = 0;
	p->role_num = 0;
	return 0;
}

int calc_paticial(role * r, struct list_head * role_list0, 
					const ctx * ctxp)
{
	assert(r != NULL);
	//begin
	if(role_list0 == NULL){
		r->freq += (1 + ROLE_BI(ctxp->num - 1, r->id, ctxp));
		r->prev = 0;
		return 0;
	}
	
	struct list_head * rlist = NULL;
	role * r0 = NULL;
	unsigned int min = _I_;
	unsigned int temp;
	list_for_each(rlist, role_list0){
		r0 = list_entry(rlist, role, list);
		temp = r0->freq + ROLE_BI(r0->id, r->id, ctxp);
		if(temp < min){
			min = temp;
			r->prev = r0;
		}
	}
	LOGIT(LV_DEBUG, "%d", min);
	r->freq += min;
	return 0;
}

int viterbi_path(mod * p, role * r, const ctx * ctxp)
{
	int i = p->role_num;
	p->role_seq[i--] = 0;
	while(r->prev){
		p->role_seq[i--] = ctx_mapping(ctxp, r->prev->id);
		r = r->prev;
	}
	assert(i == -1);
	return 0;
}

int viterbi(mod * p, struct list_head * list0, struct list_head *  list, 
				vertex * v, enum TAG_STATE st, const ctx * ctxp)
{
	assert(p != NULL && list != NULL && v != NULL && ctxp != NULL);
	//add role type 0 to role_list
	if(role_push(v, st, 0, v->freq, p) < 0){
		return -1;
	}

	struct list_head * item = NULL;
	role * r = NULL;
	list_for_each(item, list){
		r = list_entry(item, role, list);
		//calc paticial freq & prev
		calc_paticial(r, list0, ctxp);
	}

	return 0;
}

int fetch_nr(mod * p)
{
	char pattern[][5]={ "BBCD","BBC","BBE","BBZ","BCD","BEE","BE","BG",
		"BXD","BZ", "CDCD","CD","EE", "FB", "Y","XD",""};
	//BBCD:姓+姓+名1+名2;
	//BBE: 姓+姓+单名;
	//BBZ: 姓+姓+双名成词;
	//BCD: 姓+名1+名2;
	//BE:  姓+单名;
	//BEE: 姓+单名+单名;韩磊磊
	//BG:  姓+后缀
	//BXD: 姓+姓双名首字成词+双名末字
	//BZ:  姓+双名成词;
	//B:	 姓
	//CD:  名1+名2;
	//EE:  单名+单名;
	//FB:  前缀+姓
	//XD:  姓双名首字成词+双名末字
	//Y:   姓单名成词
	int pattern_len[]={4,3,3,3,3,3,2,2,3,2,4,2,2,2,1,2,0};
	int i = 0;
	int j = 0;

	while(i < p->role_num){
		int k = 0;
		for(j=0; k==0 && pattern_len[j]>0; j++){
			if(strncmp(pattern[j], p->role_seq+i, pattern_len[j])!=0){
				continue;
			}
			k = pattern_len[j];
		}
		if(k > 0){
			unsigned short len = 0;
			if(p->role_off[i + k] == 0){
				len = p->cnum - p->role_off[i];
			}else{
				len = p->role_off[i + k] - p->role_off[i];
			}
			if(mod_push(p, p->role_off[i], len, UN_PER, PUSH_UNKNOWN) < 0){
				return -1;
			}
			i += pattern_len[k];
		}else{
			i ++;
		}
	}
	return 0;
}

int fetch_ns_tr(mod * p, enum UNKNOWN_TYPE st)
{
//[B+C*D*][C*D*]
	int i = 0;
	while(i < p->role_num){
		int k = 0;
		if(p->role_seq[i] == 'B'){
			k = 1;
			while(p->role_seq[i+k] == 'B' && i+k < p->role_num){
				k ++;
			}
			while(p->role_seq[i+k] == 'C' && i+k < p->role_num){
				k ++;
			}
			while(p->role_seq[i+k] == 'D' && i+k < p->role_num){
				k ++;
			}
		}else if(p->role_seq[i+k] == 'C'){
			k = 1;
			while(p->role_seq[i+k] == 'C' && i+k < p->role_num){
				k ++;
			}
			while(p->role_seq[i+k] == 'D' && i+k < p->role_num){
				k ++;
			}
		}
		if(k > 1){
			unsigned short len = 0;
			if(p->role_off[i + k] == 0){
				len = p->cnum - p->role_off[i];
			}else{
				len = p->role_off[i + k] - p->role_off[i];
			}
			if(mod_push(p, p->role_off[i], len, st, PUSH_UNKNOWN) < 0){
				return -1;
			}
			i += k;
		}else{
			i ++;
		}
	}
	return 0;
}

int oov(mod * p)
{
	assert(p != NULL);

	struct list_head * list = p->graph;		//current graph list
	assert(!list_empty(list) && list->next == list->prev);

	vertex * v0 = NULL;
	vertex * v = NULL;
	do{
		assert(!list_empty(list) && list->next == list->prev);
		if(list->next == NULL){
			return -1;
		}

		v = list_entry(list->next, vertex, list);
		//add other role
		int rolei = v->rolei;
		while(rolei){
			const tag_node * tagp = TAGAT(p->datp, rolei);
			if(role_push(v, TAGK(tagp->id), TAGV(tagp->id), tagp->freq, p) < 0){
				return -2;
			}
			rolei = tagp->tagi;
		}
		p->role_off[p->role_num ++] = v->off;
		#ifdef OOV_NR
		if(viterbi(p, v0==NULL?NULL:&v0->nr_list, &v->nr_list, 
					v, TAG_NR, p->nrp)){
			return -3;
		}
		#endif
		
		#ifdef OOV_NS
		if(viterbi(p, v0==NULL?NULL:&v0->ns_list, &v->ns_list, 
					v, TAG_NS, p->nsp)){
			return -4;
		}
		#endif

		#ifdef OOV_TR
		if(viterbi(p, v0==NULL?NULL:&v0->tr_list, &v->tr_list, 
					v, TAG_TR, p->trp)){
			return -5;
		}
		#endif

		v0 = v;
		list = list + v->len;
	}while(v->len != 0);
	p->role_num --;

	role * r = NULL;

	#ifdef OOV_NR
	r = list_entry(v->nr_list.next, role, list);

	if(viterbi_path(p, r, p->nrp) < 0){
		return -6;
	}
	if(fetch_nr(p) < 0){
		return -7;
	}
/*
	int i = 0;
	for(i=0; i < p->role_num; i++){
		fprintf(stderr, "%c[%d]\t", p->role_seq[i], p->role_off[i]);
	}
	fprintf(stderr, "\n");
*/
	#endif

	#ifdef OOV_TR
	r = list_entry(v->tr_list.next, role, list);

	if(viterbi_path(p, r, p->trp) < 0){
		return -8;
	}
	if(fetch_ns_tr(p, UN_PER) < 0){
		return -9;
	}
/*
	int i = 0;
	for(i=0; i < p->role_num; i++){
		fprintf(stderr, "%c[%d]\t", p->role_seq[i], p->role_off[i]);
	}
	fprintf(stderr, "\n");
*/
	#endif

	#ifdef OOV_NS
	r = list_entry(v->ns_list.next, role, list);

	if(viterbi_path(p, r, p->nsp) < 0){
		return -6;
	}
	if(fetch_ns_tr(p, UN_LOC) < 0){
		return -7;
	}
/*
	int i = 0;
	for(i=0; i < p->role_num; i++){
		fprintf(stderr, "%c[%d]\t", p->role_seq[i], p->role_off[i]);
	}
	fprintf(stderr, "\n");
*/
	#endif

	return 0;
}

static int mod2result(mod * p)
{
	assert(p != NULL);

	int off = 0;
	vertex * v = NULL;
	struct list_head * list = NULL;
	while(off < p->cnum){
		list = p->graph + off;
		v = list_entry(list->next, vertex, list);
		if(v == NULL){
			return -1;
		}
		result_push(p->resp, v->len);
		off += v->len;
	}
	return off;
}

int mod_kbest1(mod * p);
int mod_kbest2(mod * p);
int mod_kbest3(mod * p);
#define mod_kbest(p) mod_kbest2(p)
int mod_do(mod * p)
{
	int ret;
	assert(p != NULL);
	ret = mod_kbest(p);//seg time
	if(ret < 0){
		LOGIT(LV_ERROR, "kbest %d", ret);
		return -1;
	}
	#if (defined OOV_NR) ||  (defined OOV_NS) || (defined OOV_TR) 
	ret = oov(p);
	if(ret < 0){
		LOGIT(LV_ERROR, "viterbi %d", ret);
		return -2;
	}
	ret = mod_kbest(p);//seg time
	if(ret < 0){
		LOGIT(LV_ERROR, "kbest2 %d", ret);
		return -3;
	}
	#endif
	ret = mod2result(p);
	if(ret < 0){
		LOGIT(LV_ERROR, "mod2result %d", ret);
		return -4;
	}
	return ret;
}

//short path methods start from here
//dijkstra
int mod_kbest1(mod * p)
{
	assert(p != NULL);
	
	memset(p->closed, 0, sizeof(p->closed));
	memset(p->dist, 0xFF, sizeof(p->dist));

	unsigned int w;
	//1.beging
	struct list_head * list = NULL;
	vertex * v = NULL;
	
	list_for_each(list, p->graph){
		v = list_entry(list, vertex, list);
		p->dist[v->vidx] = mod_get_weight(p, NULL, v);
		p->prev[v->vidx] = VIDX_BEG;
	}

	p->closed[VIDX_BEG] = 1;
	p->prev[VIDX_BEG] = (unsigned short)(_I_);
	unsigned int close_num = 1;
	
	//extend vertex to closed
	for(close_num = 1; close_num < p->vnum; close_num ++){
		unsigned int min = _I_;
		unsigned short ui = (unsigned short)_I_;

		//find increase shortest path
		//TODO: advance range i
		int i;
		for(i = 0; i < p->vnum; i ++){
			if(p->closed[i] == 0 && p->dist[i] < min){
				min = p->dist[i];
				ui = i;
			}
		}
		if(ui == (unsigned short)_I_){
			assert(0);
			return -1;
		}

		//move i to closed
		p->closed[ui] = 1;
		if(ui == VIDX_END){
			if(kbest_path(p) < 0){
				return -2;
			}
			return 0;
		}

		//update dist of vertex linked by ui
		vertex * u = vmap_get(p, ui);
		if(u == NULL){
			return -3;
		}

		assert((p->graph + u->off + u->len)->next != NULL);
		if((p->graph + u->off + u->len)->next == NULL){
			continue;
		}
		list_for_each(list, p->graph + u->off + u->len){
			v = list_entry(list, vertex, list);
			if(p->closed[v->vidx] != 0){
				continue;
			}
			w = mod_get_weight(p, u, v);
			LOGIT(LV_DEBUG, "%d[%u-%u]:%d[%u-%u] %d\t", 
				u->vidx, u->off, u->len, v->vidx, v->off, v->len, 
				w);
			//FIXME: judge first
			if(p->dist[v->vidx] > w + min){
				p->dist[v->vidx] = w + min;
				p->prev[v->vidx] = ui;
			}
		}
	}
	return 0;
}

int dfs_visit(mod * p, vertex * v)
{
	if(v->len == 0){
		goto DONE;
	}
	v->color = COLOR_GRAY;
	assert((p->graph + v->off + v->len)->next != NULL);
	if((p->graph + v->off + v->len)->next == NULL){
		//dict warn
		return -1;
	}
	struct list_head * list = NULL;
	list_for_each(list, p->graph + v->off + v->len){
		vertex * u = list_entry(list, vertex, list);
		if(u->color == COLOR_WHITE && dfs_visit(p, u) < 0){
			return -2;
		}
	}
	list_add(&v->top_list, &p->top);
DONE://list with out tail
	v->color = COLOR_BLACK;
	return 0;
}

int dfs(mod * p)
{
	INIT_LIST_HEAD(&p->top);
	struct list_head * list = NULL;
	if(p->graph->next == NULL){
		return -1;
	}
	list_for_each(list, p->graph){
		vertex * v = list_entry(list, vertex, list);
		if(v->color == COLOR_WHITE && dfs_visit(p, v) < 0){
			return -2;
		}
	}
	return 0;
}

#define relex(p, u, v, w)	\
		do{		\
			if(p->dist[v->vidx] > p->dist[u->vidx] + w){	\
				p->dist[v->vidx] = p->dist[u->vidx] + w;	\
				p->prev[v->vidx] = u->vidx;		\
			}	\
		}while(0)

int relex_by_order(mod * p)
{
	memset(p->dist, 0xFF, sizeof(p->dist));
	struct list_head * list = NULL;
	struct list_head * next = NULL;
	vertex * u = NULL;
	vertex * v = NULL;
	unsigned int w = 0;
	//begin
	list_for_each(next, p->graph){
		v = list_entry(next, vertex, list);
		w = mod_get_weight(p, NULL, v);
		p->dist[v->vidx] = w;
		p->prev[v->vidx] = VIDX_BEG;
	}
	//foreach
	list_for_each(list, &p->top){
		u = list_entry(list, vertex, top_list);
	//	printf("[%d]:%d\n", u->off, u->len);
		assert((p->graph + u->off + u->len)->next != NULL);
		if((p->graph + u->off + u->len)->next == NULL){
			//dict warn
			continue;
		}
		list_for_each(next, p->graph + u->off + u->len){
			v = list_entry(next, vertex, list);
			w = mod_get_weight(p, u, v);
			LOGIT(LV_DEBUG, "%d[%u-%u]:%d[%u-%u] %d\t", 
				u->vidx, u->off, u->len, v->vidx, v->off, v->len, 
				w);
			relex(p, u, v, w);
		}
	}
	return 0;
}

//top sort
int mod_kbest2(mod * p)
{
	//top sort
	if(dfs(p) < 0){
		return -1;
	}
	//relex by order
	if(relex_by_order(p) < 0){
		return -2;
	}
	if(kbest_path(p) < 0){
		return -3;
	}
	return 0;
}

//heap start from 1
#define _cmp(a, b) ((a) < (b))
int hpush(mod * p, unsigned short vidx, unsigned int w)
{
	if(p->map[vidx] && !_cmp(w, p->dist[p->map[vidx]])){
		return 1;
	}
	unsigned short i;//heap idx
	//shift up
	for(i=(p->map[vidx]?p->map[vidx]:++p->hsize); 
			i>1 && _cmp(w, p->dist[i>>1]); 
			i>>=1){
		p->dist[i] = p->dist[i>>1];
		p->ind[i] = p->ind[i>>1];
		p->map[p->ind[i]] = i;
	}
	p->dist[i] = w;
	p->ind[i] = vidx;
	p->map[vidx] = i;
	return 0;
}

int hpop(mod * p, unsigned short * vidxp, unsigned int * wp)
{
	unsigned short i,c;
	if(p->hsize < 1)
		return 1;
	//shift down
	*vidxp = p->ind[1];
	*wp = p->dist[1];
	for (i=1,c=2; c<p->hsize; i=c,c<<=1){
		c += (c < p->hsize - 1 && _cmp(p->dist[c+1],p->dist[c]));
		if(!_cmp(p->dist[c], p->dist[p->hsize]))
			break;
		p->dist[i] = p->dist[c];
		p->ind[i] = p->ind[c];
		p->map[p->ind[i]] = i;
	}
	p->dist[i] = p->dist[p->hsize];
	p->ind[i] = p->ind[p->hsize];
	p->map[p->ind[i]] = i;
	p->hsize --;
	return 0;
}	

int mod_kbest3(mod * p)
{
	p->hsize = 0;
	memset(p->ind, 0, sizeof(p->ind));
	memset(p->map, 0, sizeof(p->map));
	memset(p->closed, 0, sizeof(p->closed));

	unsigned int w;
	//1.beging
	struct list_head * list = NULL;
	vertex * v = NULL;
	
	list_for_each(list, p->graph){
		v = list_entry(list, vertex, list);
		w = mod_get_weight(p, NULL, v);
		hpush(p, v->vidx, w);
		p->prev[v->vidx] = VIDX_BEG;
	}

	p->closed[VIDX_BEG] = 1;
	p->prev[VIDX_BEG] = (unsigned short)(_I_);
	unsigned int close_num = 1;
	
	//extend vertex to closed
	for(close_num = 1; close_num < p->vnum; close_num ++){
		unsigned int min;
		unsigned short ui;

		//find increase shortest path
		if(hpop(p, &ui, &min) != 0){
			return -1;
		}

		//move i to closed
		p->closed[ui] = 1;
		if(ui == VIDX_END){
			if(kbest_path(p) < 0){
				return -2;
			}
			return 0;
		}

		//update dist of vertex linked by ui
		vertex * u = vmap_get(p, ui);
		if(u == NULL){
			return -3;
		}

		assert((p->graph + u->off + u->len)->next != NULL);
		if((p->graph + u->off + u->len)->next == NULL){
			//dict warn
			continue;
		}
		list_for_each(list, p->graph + u->off + u->len){
			v = list_entry(list, vertex, list);
			if(p->closed[v->vidx] != 0){
				continue;
			}
			w = mod_get_weight(p, u, v);
			LOGIT(LV_DEBUG, "%d[%u-%u]:%d[%u-%u] %d\t", 
				u->vidx, u->off, u->len, v->vidx, v->off, v->len, 
				w);
			if(hpush(p, v->vidx, w+min) == 0){
				p->prev[v->vidx] = ui;
			}
		}
	}
	return 0;
}

